package com.kevin.Code.DFS;

/**
 * @author Vinlee Xiao
 * @Classname UniquePathsii
 * @Description Leetcode 63 不同的路径 动态规划  中等难度 有思路 但是超过时间限制
 * @Date 2021/10/1 10:44
 * @Version 1.0
 */
public class UniquePathsii {

    int pathNum = 0;

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {

        dfs(obstacleGrid, 0, 0);
        return pathNum;

    }


    public int uniquePathsWithObstacles1(int[][] obstacleGrid) {

        int row = obstacleGrid.length;
        int col = obstacleGrid[0].length;

        //设置滚动数组 用于存储结果数
        int[] result = new int[col];

        result[0] = obstacleGrid[0][0] == 0 ? 1 : 0;

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {

                //如果当前坐标为障碍物
                if (obstacleGrid[i][j] == 1) {
                    result[j] = 0;
                    continue;
                }

                if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {
                    result[j] = result[j] + result[j - 1];
                }

            }

        }

        return result[col - 1];

    }

    /**
     * 深度优先遍历的方法超时
     *
     * @param obstacleGrid
     * @param startX
     * @param startY
     */
    public void dfs(int[][] obstacleGrid, int startX, int startY) {


        if (obstacleGrid[startX][startY] != 1 && startX == obstacleGrid.length - 1 && startY == obstacleGrid[0].length - 1) {

            pathNum++;
            return;
        }
        //循环结束条件
        if (startX > obstacleGrid.length - 1 || startY > obstacleGrid[0].length - 1 || obstacleGrid[startX][startY] == 1) {

            return;
        }

        //向下
        dfs(obstacleGrid, startX + 1, startY);
        //向右
        dfs(obstacleGrid, startX, startY + 1);

    }

    /**
     * @param obstacleGrid
     * @return
     */
    public int uniquePathsWithObstacles2(int[][] obstacleGrid) {

        int row = obstacleGrid.length;
        int col = obstacleGrid[0].length;
        //设置滚动数组 用于存储结果数
        int[][] result = new int[row][col];
//        System.out.println(obstacleGrid[0][0]);
        result[0][0] = obstacleGrid[0][0] == 0 ? 1 : 0;
//        System.out.println(result[0][0]);

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {

                //跳过执行
                if (obstacleGrid[i][j] == 1) {
                    continue;
                }

                if (i - 1 >= 0 && obstacleGrid[i - 1][j] == 0) {

                    result[i][j] = result[i][j] + result[i - 1][j];
//                    System.out.println(result[i][j]);
                }

                if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {
                    result[i][j] = result[i][j] + result[i][j - 1];
//                    System.out.println(result[i][j]);
                }

            }

        }

        return result[row - 1][col - 1];

    }


    public static void main(String[] args) {
        UniquePathsii uniquePathsii = new UniquePathsii();
        int[][] num = new int[][]{{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};

        int i = uniquePathsii.uniquePathsWithObstacles2(num);
        System.out.println(i);
    }
}
